//给你一个链表数组，每个链表都已经按升序排列。 
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。 
//
// 
//
// 示例 1： 
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
// 
//
// 示例 2： 
//
// 输入：lists = []
//输出：[]
// 
//
// 示例 3： 
//
// 输入：lists = [[]]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] 按 升序 排列 
// lists[i].length 的总和不超过 10^4 
// 
// Related Topics 链表 分治 堆（优先队列） 归并排序 
// 👍 1566 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {

	// 递归方法
	//var root *ListNode // 返回最小的节点作为根节点
	//index := -1 // 记录最小节点坐标
	//
	//for i, n := range lists {
	//	if n == nil {
	//		continue
	//	}
	//
	//	if root == nil {
	//		root = n
	//		index = i
	//		continue
	//	}
	//
	//	if n.Val < root.Val {
	//		root = n
	//		index = i
	//	}
	//}
	//
	//if index == -1 {
	//	return nil
	//}
	//
	//// 后移被选取的node
	//lists[index] = lists[index].Next
	//
	//// 递归
	//root.Next = mergeKLists(lists)
	//
	//return root

	// 迭代方法

	root := new(ListNode)
	pre := root

	num := len(lists)
	nilNum := 0

	for nilNum != num {
		nilNum = 0 // 重置为nil计数

		min := int(^uint(0) >> 1)  // 给个大值
		index := -1
		for i := range lists {
			if lists[i] == nil {
				nilNum++
				continue
			}

			if lists[i].Val < min {
				min = lists[i].Val
				index = i
			}
		}

		if nilNum != num {
			pre.Next = lists[index]	// 填值
			pre = pre.Next // 位移pre
			lists[index] = lists[index].Next // 位移已使用的节点
		}
	}

	return root.Next
}
//leetcode submit region end(Prohibit modification and deletion)
